﻿/*
 * 有一个队列Q和一个空栈S，将队列中的元素逆置。
 * 操作步骤：队列中的元素都出队并依次入栈到S，然后S中的元素依次出栈并入队到Q
 */

#define MaxSize 4
typedef int ElemType;

typedef struct {
    ElemType data[MaxSize];
    int front, rear;
} Queue;

void InitQueue(Queue &Q) {
    Q.front = Q.rear = 0;
}

int QueueLength(Queue Q) {
    return (Q.rear - Q.front + MaxSize) % MaxSize;
}

bool QueueEmpty(Queue Q) {
    if (Q.front == Q.rear)
        return true;
    return false;
}

bool EnQueue_Sq(Queue &Q, ElemType e) {
    if ((Q.rear + 1) % MaxSize == Q.front)  // 队满，报错
        return false;
    Q.data[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MaxSize;  // 队尾指针加1取模
    return true;
}

bool DeQueue_Sq(Queue &Q, ElemType &e) {
    if (Q.front == Q.rear) return false;
    e = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;   // 队头指针加1取模
    return true;
}

bool GetHead(Queue Q, ElemType &e) {
    if (Q.front == Q.rear) return false;
    e = Q.data[Q.front];
    return true;
}

bool QueueReverse(Queue &Q) {
    int Q_len = QueueLength(Q);
    ElemType S[Q_len];  // 创建一个空栈
    int top = -1;
    while (Q.front != Q.rear) {  // 队列不为空，队列元素出队并进栈
        ElemType e = Q.data[Q.front];
        Q.front = (Q.front + 1) % MaxSize;
        S[++top] = e;
    }
    while (top != -1) {  // 栈不为空，栈元素出栈并入队
        ElemType e = S[top--];
        Q.data[Q.rear] = e;
        Q.rear = (Q.rear + 1) % MaxSize;
    }
}

int main() {
    Queue Q;
    InitQueue(Q);
    for (int i = 0; i < 5; i++) {
        EnQueue_Sq(Q, i);
    }
    QueueReverse(Q);
    return 0;
}
